1. Field of the Invention
The present invention is generally directed at network routing protocols and more particularly is directed to a source-directed on-demand network protocol that limits bandwidth consumption.
2. Description of the Background Art
On-demand routing protocols are being increasingly utilized with mobile ad-hoc networks and wired networks when a conventional base-station infrastructure is not available. On-demand routing algorithms were originally proposed for mobile ad-hoc networks, which are autonomous systems of mobile hosts connected by wireless links. These networks are useful in tactical and commercial scenarios in which there is no base-station infrastructure present. Ad-hoc radio networks, containing mobile nodes suffer from a limited amount of bandwidth, and one method of reducing the amount of bandwidth consumed is to maintain routes to only those destinations for which a router has data traffic. This reduces the number of updates that are sent in response to the constant topology changes.
However, as the use of the Internet increases, it is foreseeable that many enterprises will become solely dependent on the business activities conducted over the Internet. For example, financial services, securities exchanges, and emergency services all require reliable Internet connectivity. In such situations, it is not unusual for organizations to provide topological redundancy in the form of multiple links with separate gateway routers to the Internet. One issue with using multiple egress links is that manual configuration of internal routers would be needed to direct the default route to one of the gateway routers, which requires considerable planning and monitoring. Running an on-demand routing protocol in the routers of the network would allow routers to dynamically select different gateway routers for different destinations in the Internet. This would provide implicit load balancing, because some gateway routers can offer better paths to certain destinations. Also, the routers would transition more smoothly to any available gateway router if link to the Internet which is currently in use, were to fail. The main advantage of on-demand routing over the table-driven routing approach is that internal routers need only maintain routes for the subset of routes they are using. The flood search used by on-demand routing need only be propagated up to the edge of the organization network. This mechanism can be used to maintain routes to both internal destinations and external destinations.
All prior work in on-demand routing has focused on wireless networks and has followed three main approaches to ensuring that the routes obtained are free of long-term loops. The dynamic source routing (DSR) protocol is an example of a protocol which uses complete-path information to avoid loops. In DSR, the network is flooded with queries when a source requests a search for a route to a destination. Finding a route results in a reply being sent back in a route reply packet and the resultant routes are stored in a route cache at the sender. The sources are in charge of re-establishing routes when topology changes break existing routes to destinations.
The ad-hoc on-demand distance vector routing algorithm (AODV) is an example of using sequence numbers to avoid long-term loops. In AODV each destination maintains a sequence number that it updates every time there is a connectivity change with its neighbors. A router accepts those routes for a destination that are associated with the largest sequence number received for that destination. Routers whose routes to the given destination become broken increase the sequence number for the destination and report an infinite distance to all the neighbors using them as a next hop to the destination.
The Temporally-ordered routing algorithm (TORA) is an example of using time stamps and internodal coordination to avoid looping. TORA uses a link-reversal algorithm to maintain loop-free multipaths that are created by a query-reply process similar to the above two algorithms. TORA relies on clocks to create timestamps that maintain the relative ordering of events.
Under current on-demand routing protocols, when a destination fails or becomes unreachable from a network component, a source trying to obtain a path to the destination finds that its flood-search for the destination fails. However, the source is unable to determine whether or not it should start another flood search, which may have failed, for example, simply due to a temporary link failure induced by fading or node mobility. There are no inherent mechanisms within the current on-demand routing protocols to prevent a source from repeating its search in the event that the destination is not reachable, which we call the “search-to-infinity problem”.
It can be observed with some of today's on-demand routing protocols, that when a destination fails or becomes unreachable from a network component, a source trying to obtain a path to the destination finds that its flood-search for the given destination fails, but it is unable to determine whether or not it should start another flood search. It will be appreciated that the flood search may have failed simply due to temporary link failures induced by fading or node mobility. There are no inherent mechanisms in these on-demand routing protocols that would prevent a source from continually repeating its search in the event that the destination is not reachable, which is referred to as searching-to-infinity. This search-to-infinity problem also causes the network, either wired or wireless, to run an on-demand routing protocol that is susceptible to a unique form of attack, wherein a malicious router can indefinitely query a network for a destination that does not exist, thus causing network congestion due to queries. Consequently, external mechanisms are used today in order to stop sources from sending unnecessary queries. In DSR and AODV, routers do not keep state about the search queries in progress, and the application accessing the on-demand routing service must implement a hold-down time after a search fails; however, just as it was the case in Cisco's® |GRP, it is difficult to determine an adequate length of hold-down time or the number of times a source should persist requesting a path to a destination. In addition, it will be appreciated that each source must go through the process independently. On the other hand, in TORA, routers that have processed a search query keep the state and the source need not repeat the search query multiple times.
Therefore, a need exists for an on-demand routing protocol that provides for bandwidth efficient routing without unnecessary search flooding which also affords protection from service attacks, and outages, as outlined above. The present invention satisfies those needs, as well as others, and overcomes the deficiencies of previously developed routing protocols.